#include <bits/stdc++.h>

using namespace std;

class ListNode
{
public:
    int val;
    ListNode *next;
    ListNode(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};

ListNode * reverse(ListNode * head)
{
    // write your code here
    if(head == NULL || head->next == NULL)
        return head;
    ListNode * overhead = new ListNode(head->val), * temphead;
    head = head->next;
    while(head != NULL){
        temphead = new ListNode(head->val);
        head = head->next;
        temphead->next = overhead;
        overhead = temphead;
    }
    return overhead;
}

void printListNode(ListNode * head){
    while(head != NULL){
        printf("%d\t", head->val);
        head = head->next;
    }
    printf("\n");
}

int main()
{
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    printListNode(head);
    printListNode(reverse(head));
    return 0;
}
